//
//  DivisorGame.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/24.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  1025. 除数博弈

import UIKit

/*
 1025. 除数博弈
 爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

 最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

 选出任一 x，满足 0 < x < N 且 N % x == 0 。
 用 N - x 替换黑板上的数字 N 。
 如果玩家无法执行这些操作，就会输掉游戏。

 只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。

  

 示例 1：

 输入：2
 输出：true
 解释：爱丽丝选择 1，鲍勃无法进行操作。
 示例 2：

 输入：3
 输出：false
 解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
 */

class DivisorGame: NSObject {
    //最简单的解法
    func divisorGame(_ N: Int) -> Bool {
        return N%2 == 0
    }
    
    //题目分析
    /*
     当N = 1时候，爱丽丝无法选择，爱丽丝败。-------->先手失败
     当N = 2时候，爱丽丝只能选择1，剩余1。鲍勃无法选择，爱丽丝胜利。-------->先手胜利
     当N = 3时候，爱丽丝只能选择1，剩余2。根据N=2的情况可知，轮到N=2状态的那个人肯定胜利，因此爱丽丝败。-------->先手失败
     当N = 4时候，爱丽丝可以选1或者2。
                //以下就是心理博弈内容
                如果选择1，那么剩余3，由上面可知轮到N=3状态先手会失败，那么鲍勃失败，爱丽丝胜利；
                如果选择2，那么剩余2，由上面可知轮到N=2状态先手会胜利，那么爱丽丝就能胜利。
                //
                题目中给出两个玩家都以最佳状态参与游戏的条件，可知爱丽丝肯定会选择1，然后给鲍勃一个先手必败的情况。因此此时爱丽丝胜利。
                -------->先手胜利
        
     当N = 5时候，爱丽丝只能选择1，剩余4。由上面可知轮到N=4状态先手会胜利，那么爱丽丝就失败了。-------->先手失败
     当N = 6时候，爱丽丝可以选择1，2，3
                //以下是心理博弈内容
                如果选择1，那么剩余5。由上可知轮到N=5状态先手会失败，那么爱丽丝就胜利；
                如果选择2，那么剩余4。由上可知轮到N=4状态先手会胜利，那么爱丽丝就失败；
                如果选择3，那么剩余3。由上可知轮到N=3状态先手会失败，那么爱丽丝就胜利；
                //
                题目中给出两个玩家都以最佳状态参与游戏的条件，可知爱丽丝肯定会选择1或者3，然后给鲍勃一个先手必败的情况。因此此时爱丽丝胜利。
                -------->先手胜利
     
     当N = 7时候，爱丽丝只能选择1，剩余6。由上面可知轮到N=6状态先手会胜利，那么鲍勃胜利，爱丽丝失败。-------->先手失败
     ······
     */
    
    //综上，我们可以用动态规划的思想来解题
    /*
     设置f(i)表示在当前处在数字等于i的时候，先手是处于胜利还是失败的状态。true表示先手必胜，false表示先手必败。
     根据题目可知f(1) = false ; f(2) = true
     
     当Alice处于 N = k 的状态时，她的下一步操作必然使得Bob处于 N = m(m<k) 的状态。我们就根据上面推出来的条件可知
     我们只看看是否存在一个m是必败的状态，如果有，那么Alice就可以直接选它，来使自己获胜。
     如果没有任何一个m是必败的状态，那么无论Alice怎么选，最后都让Bob处于必胜的状态，那么Alice就输了。
     
     我们枚举(0,i)中i的因数j，看看是否存在f(i-j)是必败情况即可以。
     
     补充数学芝士：
     一个数的约数除了本身，其他的不可能大于这个数的1/2。因此枚举范围可以设置为0-i/2
     奇数的约数必然是奇数。偶数的约数可奇可偶。
     
     */
    func divisorGame2(_ N: Int) -> Bool {
        var dp = [Bool](repeating: false, count: N+5) //N+5只是为了防止数组越界，在本题中没有其他含义。
        dp[1] = false
        dp[2] = true
        
        if N < 3 {
            return dp[N]
        }
        
        for i in 3 ... N {
            for j in 1 ... i/2{
                if (i%j == 0 && (dp[i-j] == false)){
                    
                    //i%j == 0表示是目标值的约数，玩家可以选择这个数字
                    //dp[i-j] == false 表示如果玩家选了这个数字，那么剩下的这个数是否是必败状态
                    
                    //两个条件都满足 那么就可以设置为true了，因为选了这个数的玩家必胜
                    dp[i] = true
                    break
                }
            }
        }
        
        return dp[N]
     }
}
